package com.kevinkk.dp;

/**
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 */

/**
 * 1. dp 数组的含义：dp[i][j] 字符串 s 中下标从 i 到 j 的子串是否为回文串
 * 2. dp 公式：
 *      c[i] == c[j]
 *          如果 i 和 j 之间只相差一个数字 那么这个子串肯定是回文串
 *          如果 i 和 j 之间相差的较大，那么需要判断 中间的子串是否是回文串
 * 3. 初始化：肯定都是初始化为 false
 * 4. 遍历顺序：需要优先确保 dp[i+1][j-1] 是被计算过的，因此 i 得倒叙遍历 j 正序遍历即可
 */
public class PalindromicSubstrings {
    class Solution {
        public int countSubstrings(String s) {
            char[] c = s.toCharArray();
            boolean[][] dp = new boolean[c.length][c.length];
            int res = 0;

            for(int i = c.length-1; i >= 0; i--){
                for(int j = i; j < c.length; j++){
                    if(c[i] == c[j]){
                        if(j - i <= 1 || dp[i+1][j-1]){
                            dp[i][j] = true;
                            res ++;
                        }
                    }
                }
            }

            return res;
        }
    }
}
